import { random, swap } from 'helper/sortTest'

/**
 * NOTE: 快速排序, 选择一个元素为基点, 那么比基点 大的数放在一边, 比其小的数放在另一边
 * partition: 将数组分区,
 * 当前元素: i,l,j
 */

// 当一个有序的列表, 那么就会出现退化为 O(n^2)
export function quickSort(arr: number[]) {
  __quickSort(arr, 0, arr.length - 1)
}

// 对 arr[l...r] 进行快排
function __quickSort(arr: number[], l: number, r: number) {
  if (l >= r) {
    return
  }

  let p = partition(arr, l, r)
  __quickSort(arr, l, p - 1)
  __quickSort(arr, p + 1, r)
}

function partition(arr: number[], l: number, r: number): number {
  // 当一个近乎有序的数组会退化为 O(n^2), 避免退化为 O(n^2) => 随机选择基点可以解决
  let index = random(l, r) // 随机选择基点
  swap(arr, l, index)
  let v = arr[l] // 基点
  // arr [l+1...j-1] < v; arr [j+1...i) > v
  let j = l
  for (let i = l + 1; i <= r; i++) {
    if (arr[i] < v) {
      if (j + 1 === i) {
        j++
        continue
      }
      swap(arr, j + 1, i)
      j++
    }
  }

  swap(arr, l, j)

  return j
}

export function quickSortEnhance(arr: number[]) {
  __quickSort2(arr, 0, arr.length - 1)
}

function __quickSort2(arr: number[], l: number, r: number) {
  if (l >= r) {
    return
  }

  let p = partition2(arr, l, r)
  __quickSort2(arr, l, p - 1)
  __quickSort2(arr, p + 1, r)
}

function partition2(arr: number[], l: number, r: number): number {
  // 当一个近乎有序的数组会退化为 O(n^2), 避免退化为 O(n^2) => 随机选择基点可以解决
  let index = random(l, r) // 随机选择基点
  swap(arr, l, index)
  let v = arr[l] // 基点
  // arr [l+1...i) <= v; arr [j...r] >= v
  let i = l + 1
  let j = r
  while (true) {
    while (i <= r && arr[i] < v) {
      i++
    }
    while (j >= l + 1 && arr[j] > v) {
      j--
    }
    if (i > j) {
      break
    }
    swap(arr, i, j)
    i++
    j--
  }
  swap(arr, l, j)
  return j
}

// 三路快速排序 three-way
// arr[l+1 ... lt ] < v ; arr[lt+1...i-1] == v ; arr[gt...r] > v
// 当前元素 e = arr[i]
export function quickSortThreeWay(arr: number[]) {
  __quickSort3(arr, 0, arr.length - 1)
}

// arr[l+1 ... lt) < v ; arr[lt...gt-1] == v ; arr[gt...r] > v
function __quickSort3(arr: number[], l: number, r: number) {
  if (l >= r) {
    return
  }

  // partition
  let index = random(l, r) // 随机选择基点
  swap(arr, l, index)
  let v = arr[l] // 基点

  let lt = l // arr[l+1...lt], 初始为空

  let gt = r + 1 // arr[gt...r] 初始为空

  let i = l + 1 // arr[lt+1 ... i ] == v

  while (i < gt) {
    if (arr[i] < v) {
      swap(arr, i, lt + 1)
      lt++
      i++
    } else if (arr[i] > v) {
      swap(arr, i, gt - 1)
      gt--
    } else { // arr[i] === v
      i++
    }
  }
  swap(arr, l, lt)
  __quickSort3(arr, l, lt - 1)
  __quickSort3(arr, gt, r)
}

/**
 * 分治算法: 分割成同等结构的问题; 逐一解决, 那么主问题也就解决了
 */
